YES 1.31 H-Termination proof of /home/matraf/haskell/eval_FullyBlown_Fast/List.hs
H-Termination of the given Haskell-Program with start terms could successfully be proven:



HASKELL
  ↳ BR

mainModule List
  ((isSuffixOf :: [Float ->  [Float ->  Bool) :: [Float ->  [Float ->  Bool)

module List where
  import qualified Maybe
import qualified Prelude

  isPrefixOf :: Eq a => [a ->  [a ->  Bool
isPrefixOf [] _ True
isPrefixOf [] False
isPrefixOf (x : xs) (y : ysx == y && isPrefixOf xs ys

  isSuffixOf :: Eq a => [a ->  [a ->  Bool
isSuffixOf x y reverse x `isPrefixOf` reverse y


module Maybe where
  import qualified List
import qualified Prelude



Replaced joker patterns by fresh variables and removed binding patterns.

↳ HASKELL
  ↳ BR
HASKELL
      ↳ COR

mainModule List
  ((isSuffixOf :: [Float ->  [Float ->  Bool) :: [Float ->  [Float ->  Bool)

module List where
  import qualified Maybe
import qualified Prelude

  isPrefixOf :: Eq a => [a ->  [a ->  Bool
isPrefixOf [] vw True
isPrefixOf vx [] False
isPrefixOf (x : xs) (y : ysx == y && isPrefixOf xs ys

  isSuffixOf :: Eq a => [a ->  [a ->  Bool
isSuffixOf x y reverse x `isPrefixOf` reverse y


module Maybe where
  import qualified List
import qualified Prelude



Cond Reductions:
The following Function with conditions
undefined 
 | False
 = undefined

is transformed to
undefined  = undefined1

undefined0 True = undefined

undefined1  = undefined0 False



↳ HASKELL
  ↳ BR
    ↳ HASKELL
      ↳ COR
HASKELL
          ↳ Narrow

mainModule List
  (isSuffixOf :: [Float ->  [Float ->  Bool)

module List where
  import qualified Maybe
import qualified Prelude

  isPrefixOf :: Eq a => [a ->  [a ->  Bool
isPrefixOf [] vw True
isPrefixOf vx [] False
isPrefixOf (x : xs) (y : ysx == y && isPrefixOf xs ys

  isSuffixOf :: Eq a => [a ->  [a ->  Bool
isSuffixOf x y reverse x `isPrefixOf` reverse y


module Maybe where
  import qualified List
import qualified Prelude



Haskell To QDPs


↳ HASKELL
  ↳ BR
    ↳ HASKELL
      ↳ COR
        ↳ HASKELL
          ↳ Narrow
            ↳ AND
QDP
                ↳ QDPSizeChangeProof
              ↳ QDP
              ↳ QDP
              ↳ QDP
              ↳ QDP
              ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

new_primPlusNat(Succ(ww2600), Succ(ww1800000)) → new_primPlusNat(ww2600, ww1800000)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:



↳ HASKELL
  ↳ BR
    ↳ HASKELL
      ↳ COR
        ↳ HASKELL
          ↳ Narrow
            ↳ AND
              ↳ QDP
QDP
                ↳ QDPSizeChangeProof
              ↳ QDP
              ↳ QDP
              ↳ QDP
              ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

new_primMulNat(Succ(ww15000), Succ(ww180000)) → new_primMulNat(ww15000, Succ(ww180000))

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:



↳ HASKELL
  ↳ BR
    ↳ HASKELL
      ↳ COR
        ↳ HASKELL
          ↳ Narrow
            ↳ AND
              ↳ QDP
              ↳ QDP
QDP
                ↳ QDPSizeChangeProof
              ↳ QDP
              ↳ QDP
              ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

new_primEqNat(Succ(ww15000), Succ(ww180000)) → new_primEqNat(ww15000, ww180000)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:



↳ HASKELL
  ↳ BR
    ↳ HASKELL
      ↳ COR
        ↳ HASKELL
          ↳ Narrow
            ↳ AND
              ↳ QDP
              ↳ QDP
              ↳ QDP
QDP
                ↳ QDPSizeChangeProof
              ↳ QDP
              ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

new_asAs(True, :(ww240, ww241), :(ww250, ww251), ba) → new_asAs(new_esEs(ww240, ww250, ba), ww241, ww251, ba)

The TRS R consists of the following rules:

new_sr(Neg(ww1500), Neg(ww18000)) → Pos(new_primMulNat0(ww1500, ww18000))
new_esEs(ww240, ww250, app(ty_Ratio, bh)) → new_esEs10(ww240, ww250, bh)
new_sr(Pos(ww1500), Pos(ww18000)) → Pos(new_primMulNat0(ww1500, ww18000))
new_primEqNat0(Zero, Zero) → True
new_primPlusNat1(Succ(ww2600), Succ(ww1800000)) → Succ(Succ(new_primPlusNat1(ww2600, ww1800000)))
new_esEs4(ww15, ww180) → error([])
new_primMulNat0(Zero, Succ(ww180000)) → Zero
new_primMulNat0(Succ(ww15000), Zero) → Zero
new_esEs(ww240, ww250, app(ty_[], bg)) → new_esEs9(ww240, ww250, bg)
new_esEs0(Pos(Zero), Neg(Zero)) → True
new_esEs0(Neg(Zero), Pos(Zero)) → True
new_esEs7(Float(ww150, ww151), Float(ww1800, ww1801)) → new_esEs0(new_sr(ww150, ww1800), new_sr(ww151, ww1801))
new_esEs3(ww15, ww180, ce, cf, cg) → error([])
new_primPlusNat1(Zero, Zero) → Zero
new_primEqNat0(Zero, Succ(ww180000)) → False
new_primEqNat0(Succ(ww15000), Zero) → False
new_esEs6(ww15, ww180, de, df) → error([])
new_primMulNat0(Succ(ww15000), Succ(ww180000)) → new_primPlusNat0(new_primMulNat0(ww15000, Succ(ww180000)), ww180000)
new_esEs1(ww15, ww180) → error([])
new_esEs9(ww15, ww180, db) → error([])
new_esEs0(Pos(Succ(ww1500)), Neg(ww1800)) → False
new_esEs0(Neg(Succ(ww1500)), Pos(ww1800)) → False
new_esEs11(ww15, ww180) → error([])
new_esEs0(Neg(Zero), Neg(Zero)) → True
new_esEs(ww240, ww250, app(app(ty_Either, cb), cc)) → new_esEs13(ww240, ww250, cb, cc)
new_esEs0(Pos(Zero), Neg(Succ(ww18000))) → False
new_esEs0(Neg(Zero), Pos(Succ(ww18000))) → False
new_esEs10(ww15, ww180, da) → error([])
new_esEs(ww240, ww250, app(app(app(ty_@3, bb), bc), bd)) → new_esEs3(ww240, ww250, bb, bc, bd)
new_primMulNat0(Zero, Zero) → Zero
new_esEs0(Pos(Zero), Pos(Succ(ww18000))) → False
new_esEs0(Pos(Succ(ww1500)), Pos(Zero)) → False
new_esEs(ww240, ww250, app(ty_Maybe, ca)) → new_esEs12(ww240, ww250, ca)
new_esEs5(ww15, ww180) → error([])
new_primPlusNat0(Succ(ww260), ww180000) → Succ(Succ(new_primPlusNat1(ww260, ww180000)))
new_esEs0(Neg(Succ(ww1500)), Neg(Zero)) → False
new_esEs0(Neg(Zero), Neg(Succ(ww18000))) → False
new_esEs0(Neg(Succ(ww1500)), Neg(Succ(ww18000))) → new_primEqNat0(ww1500, ww18000)
new_esEs2(ww15, ww180) → error([])
new_primEqNat0(Succ(ww15000), Succ(ww180000)) → new_primEqNat0(ww15000, ww180000)
new_primPlusNat0(Zero, ww180000) → Succ(ww180000)
new_esEs(ww240, ww250, ty_Int) → new_esEs0(ww240, ww250)
new_esEs(ww240, ww250, ty_Bool) → new_esEs5(ww240, ww250)
new_esEs(ww240, ww250, ty_Float) → new_esEs7(ww240, ww250)
new_esEs8(ww15, ww180) → error([])
new_esEs(ww240, ww250, ty_@0) → new_esEs4(ww240, ww250)
new_esEs0(Pos(Zero), Pos(Zero)) → True
new_esEs0(Pos(Succ(ww1500)), Pos(Succ(ww18000))) → new_primEqNat0(ww1500, ww18000)
new_esEs(ww240, ww250, ty_Ordering) → new_esEs8(ww240, ww250)
new_primPlusNat1(Succ(ww2600), Zero) → Succ(ww2600)
new_primPlusNat1(Zero, Succ(ww1800000)) → Succ(ww1800000)
new_esEs13(ww15, ww180, dc, dd) → error([])
new_sr(Neg(ww1500), Pos(ww18000)) → Neg(new_primMulNat0(ww1500, ww18000))
new_sr(Pos(ww1500), Neg(ww18000)) → Neg(new_primMulNat0(ww1500, ww18000))
new_esEs(ww240, ww250, ty_Double) → new_esEs1(ww240, ww250)
new_esEs12(ww15, ww180, cd) → error([])
new_esEs(ww240, ww250, ty_Integer) → new_esEs2(ww240, ww250)
new_esEs(ww240, ww250, ty_Char) → new_esEs11(ww240, ww250)
new_esEs(ww240, ww250, app(app(ty_@2, be), bf)) → new_esEs6(ww240, ww250, be, bf)

The set Q consists of the following terms:

new_esEs11(x0, x1)
new_primPlusNat0(Succ(x0), x1)
new_esEs(x0, x1, app(ty_[], x2))
new_esEs(x0, x1, app(app(ty_Either, x2), x3))
new_esEs4(x0, x1)
new_primMulNat0(Zero, Zero)
new_primPlusNat1(Succ(x0), Zero)
new_esEs5(x0, x1)
new_esEs13(x0, x1, x2, x3)
new_esEs(x0, x1, app(app(app(ty_@3, x2), x3), x4))
new_primPlusNat1(Zero, Succ(x0))
new_esEs2(x0, x1)
new_esEs(x0, x1, ty_Bool)
new_esEs(x0, x1, ty_Ordering)
new_esEs0(Neg(Zero), Pos(Succ(x0)))
new_esEs0(Pos(Zero), Neg(Succ(x0)))
new_esEs0(Neg(Succ(x0)), Neg(Succ(x1)))
new_esEs(x0, x1, ty_Double)
new_esEs7(Float(x0, x1), Float(x2, x3))
new_primPlusNat1(Zero, Zero)
new_esEs(x0, x1, ty_Int)
new_sr(Pos(x0), Pos(x1))
new_esEs(x0, x1, app(ty_Maybe, x2))
new_esEs0(Neg(Zero), Pos(Zero))
new_esEs0(Pos(Zero), Neg(Zero))
new_esEs0(Pos(Succ(x0)), Pos(Succ(x1)))
new_esEs0(Pos(Succ(x0)), Pos(Zero))
new_esEs(x0, x1, app(app(ty_@2, x2), x3))
new_esEs8(x0, x1)
new_esEs10(x0, x1, x2)
new_esEs0(Pos(Succ(x0)), Neg(x1))
new_esEs0(Neg(Succ(x0)), Pos(x1))
new_primMulNat0(Succ(x0), Zero)
new_esEs6(x0, x1, x2, x3)
new_primPlusNat0(Zero, x0)
new_esEs0(Neg(Zero), Neg(Zero))
new_esEs(x0, x1, app(ty_Ratio, x2))
new_esEs(x0, x1, ty_Float)
new_esEs(x0, x1, ty_Integer)
new_esEs1(x0, x1)
new_primMulNat0(Zero, Succ(x0))
new_esEs0(Pos(Zero), Pos(Zero))
new_primPlusNat1(Succ(x0), Succ(x1))
new_primMulNat0(Succ(x0), Succ(x1))
new_primEqNat0(Zero, Succ(x0))
new_esEs9(x0, x1, x2)
new_primEqNat0(Zero, Zero)
new_esEs(x0, x1, ty_Char)
new_esEs3(x0, x1, x2, x3, x4)
new_esEs0(Neg(Succ(x0)), Neg(Zero))
new_primEqNat0(Succ(x0), Zero)
new_primEqNat0(Succ(x0), Succ(x1))
new_esEs0(Neg(Zero), Neg(Succ(x0)))
new_sr(Neg(x0), Pos(x1))
new_sr(Pos(x0), Neg(x1))
new_esEs(x0, x1, ty_@0)
new_sr(Neg(x0), Neg(x1))
new_esEs0(Pos(Zero), Pos(Succ(x0)))
new_esEs12(x0, x1, x2)

We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:



↳ HASKELL
  ↳ BR
    ↳ HASKELL
      ↳ COR
        ↳ HASKELL
          ↳ Narrow
            ↳ AND
              ↳ QDP
              ↳ QDP
              ↳ QDP
              ↳ QDP
QDP
                ↳ QDPSizeChangeProof
              ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

new_isPrefixOf(ww15, ww14, ww18, :(ww1710, ww1711), ba) → new_isPrefixOf(ww15, ww14, new_flip(ww18, ww1710, ba), ww1711, ba)

The TRS R consists of the following rules:

new_flip(ww14, ww15, ba) → :(ww15, ww14)

The set Q consists of the following terms:

new_flip(x0, x1, x2)

We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:



↳ HASKELL
  ↳ BR
    ↳ HASKELL
      ↳ COR
        ↳ HASKELL
          ↳ Narrow
            ↳ AND
              ↳ QDP
              ↳ QDP
              ↳ QDP
              ↳ QDP
              ↳ QDP
QDP
                ↳ QDPSizeChangeProof

Q DP problem:
The TRS P consists of the following rules:

new_isPrefixOf0(ww14, ww15, :(ww160, ww161), ww17, ba) → new_isPrefixOf0(new_flip(ww14, ww15, ba), ww160, ww161, ww17, ba)

The TRS R consists of the following rules:

new_flip(ww14, ww15, ba) → :(ww15, ww14)

The set Q consists of the following terms:

new_flip(x0, x1, x2)

We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs: